﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AlgoTest
{
    public class Node
    {
        public int n; // value of node
        public Node left; // left subtree
        public Node right; // right subtree
        public Node level; // level pointer (node “to the right”)
    }

    /// <summary>
    /// A node with it's depth specified
    /// </summary>
    public struct NodeWithDepth
    {
        public Node node;
        public int depth;
    }

    class NodesInTree
    {
        /// <summary>
        /// Traverses the tree with "breadth-first" algorithm using a queue and links nodes on each level.
        /// Takes about O(log(n)) of extra memory and about O(n) of time
        /// </summary>
        /// <param name="t">Root node to start from</param>
        public void linkSameLevel(Node t)
        {
            if (t == null) return;

            // the queue stores helper structs that save the node's depth either
            var queue = new Queue<NodeWithDepth>();

            queue.Enqueue(new NodeWithDepth { node = t, depth = 0 });

            int curDepth = 0;
            while (queue.Count > 0)
            {
                var curNode = queue.Dequeue();

                // when diving to the next level...
                if (curDepth != curNode.depth)
                {
                    curDepth = curNode.depth;

                    // now linking all the nodes on current level taking them from queue
                    var nodeToBeLinked = curNode.node;
                    foreach (var nodeInQueue in queue)
                    {
                        nodeToBeLinked.level = nodeInQueue.node;
                        nodeToBeLinked = nodeToBeLinked.level;
                    }
                }

                if (curNode.node.left != null)
                    queue.Enqueue(new NodeWithDepth { node = curNode.node.left, depth = curNode.depth + 1 });
                if (curNode.node.right != null)
                    queue.Enqueue(new NodeWithDepth { node = curNode.node.right, depth = curNode.depth + 1 });
            }
        }
    }
}
